// 题目描述：设计一个支持 push ，pop ，top 操作，并能在常数时间内检索到最小元素的栈。
//
// push(x) —— 将元素 x 推入栈中。
//
// pop() —— 删除栈顶的元素。
// top() —— 获取栈顶元素。
// getMin() —— 检索栈中的最小元素。
//
// 示例:
//
//   MinStack minStack = new MinStack();
// minStack.push(-2);
// minStack.push(0);
// minStack.push(-3);
// minStack.getMin(); --> 返回 -3.
// minStack.pop();
// minStack.top(); --> 返回 0.
// minStack.getMin(); --> 返回 -2.
//

// 暴力写法 时间复杂的O(n)
class MinStack {
  constructor () {
    this.stack = []
  }

  /**
   * @description 入栈方法
   * @param x 元素
   */
  push (x) {
    this.stack.push(x)
  }

  /**
   * @description 弹栈
   */
  pop () {
    this.stack.pop()
  }

  /**
   * @description 返回栈顶元素
   * @returns {*}
   */
  top () {
    const {stack } = this
    if(!stack || !stack.length) {
      return
    }
    return stack[stack.length - 1]
  }

  /**
   * @description 获取栈内最小元素
   * @returns {number}
   */
  getMin () {
    // 遍历栈内所有的元素进行比较
    let minValue = Infinity
    const {stack } = this
    for(let i = 0; i < stack.length; i++) {
      if(stack[i] < minValue) {
        minValue = stack[i]
      }
    }
    return minValue
  }
}

// 空间换时间
/**
 * 1. 创建一个辅助栈 stack2(递减栈)
 * 2. 如栈stack1 的时候判断是否比stack2栈顶元素小，小则入栈stack1的同时也入Stack2
 * 3. stack1出栈的时候 判断是否与 stack2 的栈相等，想的则stack2亦出栈
 * 4. stack2 的栈顶元素就是 stack1 的最小元素
 */
class Minstack2 {
  constructor () {
    this.stack = []
    this.stack2 = [] // 辅助栈（递减栈）
  }
  push(x) {
    this.stack.push(x)
    if(this.stack2.length === 0 ||this.stack2[this.stack2.length - 1] > x) {
      this.stack2.push(x)
    }
  }

  pop () {
    const res = this.stack.pop()
    if(res === this.stack2[this.stack2.length - 1]) {
      this.stack2.pop()
    }
  }

  top () {
    const {stack } = this
    if(!stack || !stack.length) {
      return
    }
    return stack[stack.length - 1]
  }

  getMin() {
    const {stack2 } = this
    if(!stack2 || !stack2.length) {
      return
    }
    return stack2[stack2.length - 1]
  }
}
